package com.arron.algorithm;

/**
 * @Classname Find2
 * @Date 2020/9/12 11:24
 * @Created by 刘
 *题目：
 *  请实现有重复数字的有序数组的二分查找。
    输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
 */
public class Find2 {

    public static void main(String[] args) {

        int[] a= {2,3,3,3,4,4,5};
        System.out.println(upper_bound_(7, 3, a));
    }

    public static int upper_bound_ (int n, int v, int[] a) {
        //判断数组中是否存在这个值，不存在则直接返回数组长度加一
        if (a[n - 1] < v) return n + 1;
        int high=n-1,low=0;
        int mid;
        while(high>=low){
            mid =(high+low)/2;
            if(a[mid]>=v) {
                if(mid==0||a[mid-1]<v) return mid+1;
                else high=mid;
            }
            if(a[mid]<v) low=mid+1;
        }
        return n+1;
    }

}
